When data is sent from a first computer system to a second computer system there arises a need to authenticate data. That is, the data received by the second system must be the same data that was sent from the first computer system.
In general, a user wishing to authenticate transmitted data may employ an encryption method, if the data is redundant in some fashion. The encryption method will commonly involve converting data (also referred to as plaintext or cleartext) on a sending system to an encrypted data (also referred to as cyphertext), sending the encrypted data to a receiving system, decrypting the encrypted data on a receiving system, and then checking the data. Thus, the sending system will typically include a encrypting device to encrypt the data or message, while the receiving system will include a decrypting device to decrypt the encrypted data. For digital systems, the message is defined to be a digital message, M, that is, a sequence of symbols form some alphabet. Generally, the alphabet is chosen to be the binary alphabet consisting of 0's and 1's.
Each encrypting device is an apparatus which accepts two inputs: a message M to be encrypted, and an encoding key or operator E. Each encrypting device transforms the message M in accordance with the encryption operator E to produce an encrypted version (i.e., ciphertext) C of the message M, where C=E(M).
Each decrypting device is an apparatus which accepts two inputs: a ciphertext C to be decrypted, and a decrypting key or operator D. Each decrypting device transforms the ciphertext C in accordance with the decryption operator D to produce a decrypted version M' of the ciphertext C, where M'=D(C), or M'=D(E(M)). The encrypting operator E and the decrypting operator D are selected so that M'=M for all messages M'.
Threats to authenticity may include tampering and accidental destruction. Altering data in computer systems is analogous to jamming on communications channels. Accidental destruction refers to the unintentional overwriting or deletion of data.
Data authenticity requires that an individual not be able to substitute false ciphertext for an authentic ciphertext without detection. Formally, the two requirements are: (1) it should be computationally infeasible for an individual to systematically determine an encrypting transformation E given C, even if the corresponding plaintext M is known; and (2) it should be computationally infeasible for an individual to systematically find ciphertext C' such that D(C') is valid plaintext in the set M.
A number of cryptographic and decrypting techniques are readily available to provide authentication for digital communications. One example is the standards adopted by the National Bureau of standards in Federal Register, Mar. 17, 1975, Volume 40, No. 52 and Aug. 1, 1975, Volume 40, No. 149.
Another typical method described by Diffie and Hellman in "New Directions in Cryptography," IEEE Transactions on Information Theory (November 1976), is called a public key cryptosystem. In such a system, each user, e.g. user A, places in a public file an encrypting key E.sub.A. User A keeps to himself the details of the corresponding decrypting key D.sub.A which satisfies the equation D.sub.A (E.sub.A (M))=M.
Another method is found in Rives et al. U.S. Pat. No. 4,405,829, issued on Sep. 20, 1983 (hereinafter "RSA"). Using the RSA method, a message M to be transferred is encrypted to ciphertext C by first encrypting the message M as a number N in a predetermined set, and then rasing the number N to a first predetermined power (associated with an intended receiver), and finally computing the remainder, or residue R, when the exponentiated number N is divided by the product of two predetermined prime numbers (associated with the intended receiver). The residue R is the ciphertext C. The ciphertext C is decrypted to the original message M at the decrypting terminal in a similar manner by raising the ciphertext C to a second predetermined power (associated with the intended receiver), and then computing the residue R', when the exponetiated ciphertext C is divided by the product of two predetermined prime numbers associated with the intended receiver. The residue R' corresponds to the original message M.
Current cryptosystems may also be applied to transferring individual records within databases from a sender to a receiver. A database is a collection of interrelated data on one or more mass storage devices. The collection is usually organized to facilitate efficient and accurate inquiry and update.
One such method maintains a digital signature of each record within a database. A digital signature is an encrypting of an item and typically is limited to 512 bytes, for example. Thus, in an exemplary database containing five records labeled R1, R2, R3, R4, and R5, this method stores a signature for each of the records, i.e., E(MD(R1)), E(MD(R2)), (MD(R3)), E(MD(R4), and (MD(R5)). "MD" represents a message digest. The message digest is produced when a hash function is applied to data, resulting in a unique representation that is usually smaller in size than the original text. With such a method, a receiver wishing to authenticate a record which was sent from a sender, R1 for example, would compare MD(R1) to D(E(MD(R1))), i.e., a decrypted form of E(MD(R1)), which would be accompanied by the transmission of E(MD(R1)). A disadvantage with such a method is that it requires the storage of both the records in the database and the signatures of each of the records.
In another method, a sender will maintain a signature of the entire database. For example, the sender will maintain a data structure E(MD(R1-R2+R3+R4+R5)). Thus, to authenticate the transfer of a single record from the sender to a receiver, R1 for example, the sender begins by sending R1, R2, R3, R4, R5, and E(MD(R1+R2+R3+R4+R5)) to the receiver. The receiver then compares the MD(R1+R2+R3 R4+R5)to D(E(MD(R1+R2+R3+R4+R5))) for authenticity. A disadvantage when such a system is that it requires the transmission of the entire database instead of just the record of records of interest.
In still another method, a message digest hierarchy is used to ensure authenticity. With such a method, a concatenated string of message digests and an encrypted form of the concatenated string of message digests are sent to a receiver. The process of concatenation is well known in the art. For example, in a database containing five records, i.e. R1, R2, R3, R4, and R5, two records R1 and R3 would be authenticated in the following manner. The sender would first construct a first string, i.e., MD(R1)+MD(R3). The sender would next construct a second string, i.e., E(MD(R1)+MD(R3)). The sender would concatenate the first string and the second string and send to the receiver. The sender would next parse the string into [MD(R1)+MD(R3)] and [E(MD(R1)+MiD(R3))]. The process of parsing a string is well known in the art. Lastly, the receiver would de-encrypt E(MD(R1)+MD(R3)), parse the message digests, and compare the resulting message digests for authenticity. A disadvantage with this method is again the bulky aggregate of message digests and signatures.
A method of improving the processing and storage performance of digital signature schemes is desired.